% TODO rework structure and hierarchy
\section{Целочисленные типы данных}

Целочисленный тип данных (\IT{integral}) это тип для значения, которое может быть сконвертировано в число.
Это числа, перечисления (\IT{enumerations}), булевые типы.

\subsection{Бит}

Очевидное использования бит это булевые значения: 0 для \IT{ложно/false} и 1 для \IT{true/истинно}.

Набор булевых значений можно упаковать в \glslink{word}{слово}: в 32-битном слове будет 32 булевых значения, итд.
Этот метод также называется \IT{bitmap} или \IT{bitfield}.

Но есть очевидные накладки: тасовка бит, изоляция оных, итд.
В то время как использование \glslink{word}{слова} (или типа \IT{int}) для булевого значения это не экономично,
но очень эффективно.

В среде \CCpp, 0 это \IT{false/ложно} и любое ненулевое значение это \IT{true/истинно}.
Например:

\lstinputlisting[style=customc]{fundamentals/data_types_and_numbers_RU_lst1.c}

Это популярный способ перечислить все символы в Си-строке:

\lstinputlisting[style=customc]{fundamentals/data_types_and_numbers_RU_lst2.c}

\subsection{Ниббл AKA nibble AKA nybble}

\ac{AKA} полубайт, тетрада.
Равняется 4-м битам.

Все эти термины в ходу и сегодня.

\subsubsection{Двоично-десятичный код (\ac{BCD})}
\label{BCD}

\myindex{Intel 4004}

4-битные нибблы использовались в 4-битных процессорах, например, в легендарном Intel 4004 (который использовался в
калькуляторах).

Интересно знать, что числа там представлялись в виде \IT{binary-coded decimal} (\ac{BCD}).
Десятичный 0 кодировался как 0b0000, десятичная 9 как 0b1001, а остальные значения не использовались.
Десятичное 1234 представлялось как 0x1234.
Конечно, этот способ не очень экономичный.

Тем не менее, он имеет одно преимущество: очень легко конвертировать значения из десятичного в \ac{BCD}-запакованное и назад.
BCD-числа можно складывать, вычитать, итд, но нужна дополнительная корректировка.
В x86 CPUs для этого есть редкие инструкции:
\INS{AAA}/\INS{DAA} (adjust after addition: корректировка после сложения),
\INS{AAS}/\INS{DAS} (adjust after subtraction: корректировка после вычитания),
\INS{AAM} (after multiplication: после умножения),
\INS{AAD} (after division: после деления).

\myindex{x86!\Registers!AF}
Необходимость поддерживать \ac{BCD}-числа в CPU это причина, почему существуют флаги \IT{half-carry flag} (флаг полупереноса)
(в 8080/Z80) и
\IT{auxiliary flag} (вспомогательный флаг) (\TT{AF} в x86):
это флаг переноса, генерируемый после обработки младших 4-х бит. Флаг затем используется корректирующими инструкциями.

Тот факт, что числа легко конвертировать, привел к популярности этой книги:
\InSqBrackets{Peter Abel, \IT{IBM PC assembly language and programming} (1987)}.
Но кроме этой книги, автор этих заметок, никогда не видел \ac{BCD}-числа на практике, исключая
\IT{magic numbers} (\myref{magic_numbers}),
как, например, дата чьего-то дня рождения, закодированная как 0x19791011 --- это действительно запакованное
\ac{BCD}-число.

Инструкции для \ac{BCD} в x86 часто использовались для других целей, использовались их недокументированные особенности,
например:

\begin{lstlisting}[style=customasmx86]
	cmp al,10
	sbb al,69h
	das
\end{lstlisting}

Этот запутанный код конвертирует число в пределах 0..15 в \ac{ASCII}-символ '0'..'9', 'A'..'F'.

\myparagraph{Z80}
\myindex{Z80}

Z80 был клоном 8-битного Intel 8080 CPU, и из-за экономии места, он имеет 4-битный \ac{ALU}, т.е., каждая
операция над двумя 8-битными числами происходит за два шага.
Один из побочных эффектов в том, что легко генерировать \IT{half-carry flag} (флаг полупереноса).

\subsection{Байт}

Байт, в первую очередь, применяется для хранения символов.
8-битные байты не всегда были популярны, как сейчас.
Перфоленты для телетайпов имели 5 и 6 возможных дырок, это 5 или 6 бит на байт.

\myindex{octet}
\myindex{fetchmail}
Чтобы подчеркнуть тот факт, что в байте 8 бит, байт иногда называется \IT{октетом} (\IT{octet}):
по крайней мере \IT{fetchmail} использует эту терминологию.

9-битные байты существовали на 36-битных архитектурах: 4 9-битных байта помещались в одно \glslink{word}{слово}.
Вероятно из-за этого, стандарты \CCpp говорят что в \IT{char} должно быть \IT{как минимум} 8 бит, но может быть и больше.

\subsubsection{Стандартная ASCII-таблица}

7-битная ASCII-таблица стандартная, которая содержит только 128 возможных символов.
Раннее ПО для передачи е-мейлов работало только с 7-битными ASCII-символами, так что понадобился стандарт \ac{MIME}
для кодирования сообщений в нелатинских системах письменности.
7-битные ASCII коды дополнялись битом чётности, давая в итоге 8 бит.

\IT{Data Encryption Standard} (\ac{DES}) имеет 56-битный ключ, это 8 7-битных байт,
оставляя место для бита чётности для каждого символа.

Заучивать на память всю таблицу \ac{ASCII} незачем, но можно запомнить интервалы.
\InSqBrackets{0..0x1F} это управляющие символы (непечатные).
\InSqBrackets{0x20..0x7E} это печатные.
Коды начиная с 0x80 обычно используются для нелатинских систем письменности и/или псевдографики.

Некоторые важные коды, которые легко запомнить:
0 (конец Си-строки, \TT{'\textbackslash{}0'} в C/C++);
0xA или 10 (\IT{line feed} (перевод строки), \TT{'\textbackslash{}n'} в C/C++);
0xD или 13 (\IT{carriage return} (возврат каретки), \TT{'\textbackslash{}r'} в C/C++).

0x20 (пробел) также часто запоминается.

\subsubsection{8-битные процессоры}

x86 имеют возможность работать с байтами на уровне регистров (потому что они наследники 8-битного процессора 8080),
а RISC как ARM и MIPS --- нет.

\subsection{Wide char}
\myindex{UTF-16}
\myindex{UCS-2}

Это попытка поддерживать многоязычную среду расширяя байт до 16-и бит.
Самый известный пример это ядро Windows NT и win32-функции с суффиксом \IT{W}.
Вот почему если закодировать обычный текст на английском,
то каждый латинский символ в текстовой строке будет перемежаться с нулевым байтом.
Эта кодировка также называется UCS-2 или UTF-16

Обычно, \IT{wchar\_t} это синоним 16-битного типа данных \IT{short}.

\subsection{Знаковые целочисленные и беззнаковые}

Некоторые люди могут удивляться, почему беззнаковые типы данных вообще существуют, т.к., любое беззнаковое число
можно представить как знаковое.
Да, но отсутствие бита знака в значении расширяет интервал в два раза.
Следовательно, знаковый байт имеет интервал -128..127, а беззнаковый: 0..255.
Еще одно преимущество беззнаковых типов данных это самодокументация:
вы определяете переменную, которая не может принимать отрицательные значения.

\myindex{Java}
Беззнаковые типы данных отсутствуют в Java, за что её критикуют.
Трудно реализовать криптографические алгоритмы используя булевы операции над знаковыми типами.

Значения вроде 0xFFFFFFFF (-1) часто используются, в основном, как коды ошибок.

\subsection{Слово (word)}

Слово \glslink{word}{слово} это неоднозначный термин, и обычно означает тип данных, помещающийся в \ac{GPR}.
Байты практичны для символов, но непрактичны для арифметических расчетов.

Так что, многие процессоры имеют \ac{GPR} шириной 16, 32 или 64 бит.
Даже 8-битные \ac{CPU} как 8080 и Z80 предлагают работать с парами 8-битными регистров, каждая пара формирует 16-битный
псевдорегистр
(\IT{BC}, \IT{DE}, \IT{HL}, итд.).
Z80 имеет некоторые возможности для работы с парами регистров, и это, в каком-то смысле, эмуляция 16-битного CPU.

В общем, если в рекламе CPU говорят о нем как о ``n-битном процессоре'', это обычно означает что он имеет n-битные \ac{GPR}.

Было время, когда в рекламе жестких дисков и модулей \ac{RAM} писали, что они имеют \IT{n} килослов вместо
\IT{b} килобайт/мегабайт.

Например, \IT{Apollo Guidance Computer}\footnote{\url{https://en.wikipedia.org/wiki/Apollo_Guidance_Computer}}
имел 2048 слов \ac{RAM}.
Это был 16-битный компьютер, так что там было 4096 байт \ac{RAM}.

\IT{TX-0}\footnote{\url{https://en.wikipedia.org/wiki/TX-0}} имел 64K 18-битных слов памяти на магнитных сердечниках,
т.е., 64 килослов.

\IT{DECSYSTEM-2060}\footnote{\url{https://en.wikipedia.org/wiki/DECSYSTEM-20}}
мог иметь вплоть до 4096 килослов \IT{твердотельной памяти}
(т.е., жесткие диски, ленты, итд).
Это был 36-битный компьютер, так что это 18432 килобайта или ~18 мегабайт.

\myhrule{}

\IT{int} в \CCpp почти всегда связан со \glslink{word}{словом}.
(Кроме архитектуры AMD64, где \IT{int} остался 32-битным, вероятно, ради лучшей обратной совместимости.)

\IT{int} 16-битный на PDP-11 и старых компьютерах с MS-DOS.
\IT{int} 32-битный на VAX, и на x86 начиная с 80386, итд.

И даже более того, если в программе на \CCpp{} определение типа для переменной отсутствует,
то по умолчанию подразумевается \IT{int}.
Вероятно, это наследие языка программирования B\footnote{\url{http://yurichev.com/blog/typeless/}}.

\myhrule{}

\ac{GPR} это обычно самый быстрый контейнер для переменной, быстрее чем запакованный бит, и иногда даже быстрее запакованного
байта (потому что нет нужны изоировать единственный бит/байт из \ac{GPR}).
Даже если вы используете его как контейнер для счетчика в цикле, в интервале 0..99.

\myhrule{}

В языке ассемблера, \gls{word} всё еще 16-битный для x86, потому что так было во времена 16-битного 8086.
\IT{Double word} 32-битный, \IT{quad word} 64-битный.
Вот почему 16-битные слова определяются при помощи \TT{DW} в ассемблере на x86, для 32-битных используется \TT{DD}
и для 64-битных --- \TT{DQ}.

\Gls{word} 32-битный для ARM, MIPS, итд, 16-битные типы данных называются здесь \IT{half-word} (полуслово).
Следовательно, \IT{double word} на 32-битном RISC это 64-битный тип данных.

В \IT{GDB} такая терминология: \IT{halfword} для 16-битных, \gls{word} для 32-битных и \IT{giant word} для 64-битных.

В 16-битной среде \CCpp{} на PDP-11 и MS-DOS был тип \IT{long} шириной в 32 бита, вероятно, они имели ввиду
\IT{long word} или \IT{long int}?

В 32-битных средах \CCpp{} имеется тип \IT{long long} для типов данных шириной 64 бита.

Теперь вы видите, почему термин \IT{слово} такой неоднозначный.

\subsubsection{Нужно ли использовать \IT{int}?}

Некоторые люди говорят о том, что тип \IT{int} лучше не использовать вообще, потому что его неоднозначность приводит
к ошибкам.
Например, хорошо известная библиотека \IT{lzhuf} использует тип \IT{int} в одном месте, и всё работает нормально на 16-битной
архитектуре.
Но если она портируется на архитектуру с 32-битным \IT{int}, она может падать: \url{http://yurichev.com/blog/lzhuf/}.

Более однозначные типы определены в файле \IT{stdint.h}:
\IT{uint8\_t}, \IT{uint16\_t}, \IT{uint32\_t}, \IT{uint64\_t}, итд.

\myindex{Дональд Э. Кнут}
Некоторые люди, как Дональд Э. Кнут, предлагают\footnote{\url{http://www-cs-faculty.stanford.edu/~uno/news98.html}}
более звучные слова для этих типов:\\
\IT{byte/wyde/tetrabyte/tetra/octabyte/octa}.
Но эти имена менее популярны чем ясные термины с включением символа \IT{u} (\IT{unsigned})
и числом прямо в названии типа.

\subsubsection{Компьютеры ориентированные на слово}

Не смотря на неоднозначность термина \glslink{word}{слово}, современные компьютеры всё еще ориентированы на слово:
\ac{RAM} и все уровни кэш-памяти организованы по словам а не байтам.
Впрочем, в рекламе пишут о размере именно в байтах.
% <!-- TODO word length on intel, etc... -->

Доступ по адресу в памяти и кэш-памяти выровненный по границе слова зачастую быстрее, чем невыровненный.

При разработке структур данных, от которых ждут скорости и эффективности, всегда нужно учитывать длину \glslink{word}{слова}
CPU, на котором это будет исполняться.
Иногда компилятор делает это за программиста, иногда нет.

\subsection{Регистр адреса}

Для тех, кто был воспитан на 32-битных и/или 64-битных x86, и/или RISC 90-х годов, как ARM, MIPS, PowerPC, считается
обычным, что шина адреса имеет такую же ширину как \ac{GPR} или \glslink{word}{слово}.
Тем не менее, на других архитектурах, ширина шины адреса может быть другой.

8-битный Z80 может адресовать $2^{16}$ байт, используя пары 8-битных регистров, или специальные регистры (\IT{IX}, \IT{IY}).
Регистры \IT{SP} и \IT{PC} также 16-битные.

\myindex{Cray-1}
Суперкомпьютер Cray-1 имел 64-битные GPR, но 24-битные регистры для адресов, так что он мог адресовать
$2^{24}$ (16 мегаслов или 128 мегабайт).
Память в 1970-ые была очень дорогой, так что и не ожидалось, что даже в среде суперкомпьютеров её будет больше.
Тогда зачем выделять целый 64-битный рергистр для адреса или указателя?

Процессоры 8086/8088 имели крайне странную схему адресации:
значения двух 16-битных регистров суммировались в очень странной манере, производя 20-битный адрес.
Вероятно, то было что-то вроде игрушечной виртуализации (\myref{8086_memory_model})?
8086 мог исполнять несколько программ (хотя и не одновременно).

\myindex{ARM!ARM1}
Ранний ARM1 имеет интересный артефакт:

\begin{framed}
\begin{quotation}
Another interesting thing about the register file is the PC register is missing a few bits. Since the ARM1 uses 26-bit addresses, the top 6 bits are not used. Because all instructions are aligned on a 32-bit boundary, the bottom two address bits in the PC are always zero. These 8 bits are not only unused, they are omitted from the chip entirely.
\end{quotation}
\end{framed}

( \url{http://www.righto.com/2015/12/reverse-engineering-arm1-ancestor-of.html} )

Так что, значение где в двух младших битах что-то есть, невозможно записать в регистр PC просто физически.
Также невозможно установить любой бит в старших 6 битах PC.

Архитектура x86-64 имеет 64-битные виртуальные указателя/адреса, но внутри адресная шина 48-битная
(этого достаточно для адресации 256TB памяти).

\subsection{Числа}

Для чего используются числа?

Когда вы видите как некое число/числа меняются в регистре процесса, вы можете заинтересоваться, что это число значит.
Это довольно важное качество реверс-инжинира, определять возможный тип данных по набору изменяемых чисел.

\subsubsection{Булевы значения}

Если число меняется от 0 до 1 и назад, скорее всего, это значение имеет булевый тип данных.

\subsubsection{Счетчик циклов, индекс массива}

Переменная увеличивающаяся с 0, как: 0, 1, 2, 3\dots --- большая вероятность что это счетчик цикла и/или индекс массива.

\subsubsection{Знаковые числа}

Если вы видите переменную, которая содержит очень маленькие числа, и иногда очень большие,
как 0, 1, 2, 3, и 0xFFFFFFFF, 0xFFFFFFFE, 0xFFFFFFFD,
есть шанс что это знаковая переменная в виде \IT{дополнительного кода} (\myref{sec:signednumbers}),
и последние три числа это -1, -2, -3.

\subsubsection{32-битные числа}

Существуют настолько большие числа\footnote{\url{https://en.wikipedia.org/wiki/Large_numbers}},
что для них даже существует специальная нотация (Knuth's up-arrow notation
\footnote{\url{https://en.wikipedia.org/wiki/Knuth\%27s_up-arrow_notation}}).
Эти числа настолько большие, что им нет практического применения в инженерии, науке и математике.

Почти всем инженерам и ученым зачастую достаточно чисел в формате IEEE 754 в двойной точности,
где максимальное значение близко к $1.8 \cdot 10^{308}$.
(Для сравнения, количество атомов в наблюдаемой Вселенной оценивается от $4 \cdot 10^{79}$ до $4 \cdot 10^{81}$.)

А в практическом программировании, верхний предел значительно ниже.
Если вы посмотрите в исходные коды UNIX v6 для PDP-11
\footnote{\url{http://minnie.tuhs.org/Archive/PDP-11/Distributions/research/Dennis_v6/}},
16-битные \IT{int} используются везде, а 32-битные \IT{long} не используются вообще.

Та же история была и в эпоху MS-DOS: 16-битные \IT{int} использовались почти везде (индексы массивов, счетчики циклов),
в то время как 32-битные \IT{long} использовались редко.

Во время появления x86-64, было решено оставить тип \IT{int} 32-битным, вероятно, потому что 
необходимость использования 64-битного \IT{int} еще меньше.

Я бы сказал, что 16-битные числа в интервале 0..65535, вероятно, наиболее используемые числа в программировании вообще.

Учитывая всё это, если вы видите необычно большое 32-битное значение вроде 0x87654321, большая вероятность,
что это может быть:

\begin{itemize}

\item это всё еще может быть 16-битное число, но знаковое, между 0xFFFF8000 (-32768) и 0xFFFFFFFF (-1).
% TODO: [Example](https://github.com/dennis714/random_notes/blob/master/timedate.md).
\item адрес ячейки памяти (можно проверить используя в карте памяти в отладчике);
\item запакованные байты (можно проверить визуально);
\item битовые флаги;
\item что-то связанное с (любительской) криптографией;
\item \IT{магическое число} (\myref{magic_numbers});
\item число с плавающей точкой в формате IEEE 754 (тоже легко проверить).

\end{itemize}

Та же история и для 64-битных значений.

\myparagraph{\dots так что, 16-битного \IT{int} достаточно почти для всего?}

Интересно заметить: в \InSqBrackets{\MAbrash{} глава 13}
мы можем найти множество случаев, когда 16-битных переменных просто достаточно.
В то же время, Майкл Абраш жалеет о том что в процессорах 80386 и 80486 маловато доступных регистров,
так что он предлагает хранить два 16-битных значения в одном 32-битном регистре и затем прокручивать его 
используя инструкцию \INS{ROR reg, 16} (на 80386 и позже) (\INS{ROL reg, 16} тоже будет работать) или
\INS{BSWAP} (на 80486 и позже).

Это нам напоминает как в Z80 был набор альтернативных регистров (с апострофом в конце), на которые CPU мог переключаться
(и затем переключаться назад) используя инструкцию \INS{EXX}.

\subsubsection{Размер буфера}

Когда программисту нужно обознать размер некоторого буфера, обычно используются значения вида $2^x$ (512 байт, 1024, итд.).
Значения вида $2^x$ легко опознать (\myref{2n_numbers_table}) в десятичной, шестнадцатеричной и двоичной системе.

Но надо сказать что программисты также и люди со своей десятичной культурой.
И иногда, в среде \ac{DBMS}, размер текстовых полей в БД часто выбирается в виде числа $10^x$, как 100, 200.
Они думают что-то вроде \q{Окей, 100 достаточно, погодите, лучше пусть будет 200}.
И они правы, конечно.

Максимальный размер типа данных \IT{VARCHAR2} в \oracle это 4000 символов, а не 4096.

В этом нет ничего плохого, это просто еще одно место где можно встретить числа вида $10^x$.

\subsubsection{Адрес}

Всегда хорошая идея это держать в памяти примерную карту памяти процесса, который вы отлаживаете.
Например, многие исполняемые файлы в win32 начинаются с 0x00401000, так что адрес вроде 0x00451230 скорее всего находится в секции с исполняемым кодом.
Вы увидите адреса вроде этих в регистре \TT{EIP}.

Стек обычно расположен где-то ниже. % TODO

Многие отладчики могут показывать карту памяти отлаживаемого процесса, например: \myref{olly_memory_map_example}.

Если знчаение увеличивается с шагом 4 на 32-битной архитектуре или с шагом 8 на 64-битной,
это вероятно сдвигающийся адрес некоторых элементов массива.

Важно знать что win32 не использует адреса ниже 0x10000, так что если вы видите какое-то число ниже этой константы,
это не может быть адресом (см.также: \url{https://msdn.microsoft.com/en-us/library/ms810627.aspx}).

Так или иначе, многие отладчики могут показывать, является ли значение в регистре адресом чего-либо.
OllyDbg также может показывать ASCII-строку, если значение является её адресом.

\subsubsection{Битовые поля}

Если вы видите как в значении один (или больше) бит меняются от времени к времени, как 0xABCD1234 $\rightarrow$ 0xABCD1434 и назад,
это вероятно битовое поле (или \IT{bitmap}).

\subsubsection{Запакованные байты}

\myindex{\CStandardLibrary!strcmp()}
\myindex{\CStandardLibrary!memcmp()}
Когда \IT{strcmp()} или \IT{memcmp()} копирует буфер, они загружают/записывают 4 (или 8) байт одновременно,
так что если строка содержит \q{4321} и будет скопирована в другое место,
в какой-то момент вы увидите значение 0x31323334 в каком-либо регистре.
Это 4 запакованных байта в одном 32-битном значении.

